package com.turing.data.engine;

import java.util.AbstractMap;
import java.util.Map;
import java.util.regex.Pattern;

public class BinarySearch {

    private static int findPosForward(String content, String pattern, int power, int start) {

        //Math.pow( 2, power ) - 1 >= Integer.MAX_VALUE
        if (power >= 31) {
            return -1;
        }

        int stepSize = (int) Math.pow(2, power);

        if ((start - stepSize) < 0) {
            return -1;
        }

        int cursor = start - stepSize;
        String text = content.substring(cursor, start);
        int result = -1;

        while (power >= 0) {

            stepSize = stepSize / 2;
            if (Pattern.matches(pattern, text)) {
                result = cursor;
                cursor += stepSize;
            } else {
                cursor -= stepSize;
            }

            text = content.substring(cursor, start);
            power--;

        }

        return result;

    }

    private static int findPosBackward(String content, String pattern, int power, int end) {

        //Math.pow( 2, power ) - 1 >= Integer.MAX_VALUE
        if (power >= 31) {
            return -1;
        }

        int stepSize = (int) Math.pow(2, power);

        if ((end + stepSize) > content.length()) {
            return -1;
        }

        String text = content.substring(end, (end + stepSize));
        int cursor = end + stepSize;
        int result = -1;

        while (power >= 0) {

            stepSize = stepSize / 2;
            if (Pattern.matches(pattern, text)) {
                result = cursor;
                cursor -= stepSize;
            } else {
                cursor += stepSize;
            }
            text = content.substring(end, cursor);
            power--;

        }

        return result;

    }

    private static Map.Entry<Integer, Integer> findGlobalPos(String content, String pattern, int power, int start) {

        if (power >= 30) {
            return new AbstractMap.SimpleEntry<>(-1, -1);
        }
        int startR = start + (int) Math.pow(2, power);
        int posForward = findPosForward(content, pattern, power, startR);
        int posBackward = findPosBackward(content, pattern, power, start);
        return new AbstractMap.SimpleEntry<>(posForward, posBackward);

    }


    private static int expandForward(String content, String pattern, int power, int start) {

        int startOffset = 0;
        while (start >= startOffset && startOffset < (int) Math.pow(2, power)) {
            String text = content.substring(start - startOffset, start);
            if (Pattern.matches(pattern, text)) {
                return start - startOffset;
            }
            startOffset++;
        }
        return -1;

    }

    private static int expandBackward(String content, String pattern, int power, int end) {

        int endOffset = 0;
        while (end + endOffset <= content.length() && endOffset < (int) Math.pow(2, power)) {
            String text = content.substring(end, end + endOffset);
            if (Pattern.matches(pattern, text)) {
                return end + endOffset;
            }
            endOffset++;
        }
        return -1;

    }

    public static Map.Entry<Integer, Integer> expandGlobalPos(String content, String pattern, int power, int start) {

        if (power >= 30) {
            return new AbstractMap.SimpleEntry<>(-1, -1);
        }
        int startR = start + (int) Math.pow(2, power);
        int posForward = expandForward(content, pattern, power, startR);
        int posBackward = expandBackward(content, pattern, power, start);
        return new AbstractMap.SimpleEntry<>(posForward, posBackward);

    }

    public static void main(String[] args) {

        String content = "随着春节的临近，由暴雪娱乐制作的团队射击游戏《守望先锋》又开始了新一轮的春节促销，新皮肤、新地图、新内容的上架在带给玩家新奇的同时再度点燃了他们前往那个世界冒险与探索的热情，最近《守望先锋》又放出了新地图“巴黎之声”的先导宣传，令不少玩家都开始期待这张新地图会带来怎样的惊喜。" +
                "《守望先锋》自2016年推出以来，不仅新英雄越来越多，其不断推出的CG、漫画、小说等有关资料，也令《守望先锋》的世界观愈加清晰和完整。这种清晰和完整对一些玩家来说是增强代入感的绝佳手段，对于笔者来说，则更有利解答一些曾经令笔者迷惑的问题，" +
                "那就是——“守望先锋”为什么会被解散？" +
                "在《守望先锋》的世界观中，人类在二十一世纪将曾经的幻想变成了现实，制造出了高级人工智能机械，这些机械被简称为“智械”。在智械的帮助下，人类社会的生产力得到了巨大的发展，智械帮助人类修建高楼大厦，完成各种工作，人类在智械的帮助下迎来了新的繁荣。" +
                "但繁荣之后，危机出现了，在某一天，原本勤勤恳恳为人类工作的智械突然发起了叛乱，他们的机器军队向全世界的人类发起进攻，意图推翻人类的统治，“智械危机”爆发了。各国政府面对智械的进攻节节败退，就在这时，“守望先锋”成立了，这个组织由世界各国的精英分子和优秀战士所组成的，在守望先锋的奋战下，人类最终虽然付出了惨重的代价，但终于迎来了胜利。";
        String patternF = ".*有关资料.*";
        String patternB = ".*智械危机.*";
        int power = 8;
        int start = 280;
        long startMicro = System.nanoTime();
        int posForward = findPosForward(content, patternF, power, start);
        long endMicro = System.nanoTime();
        System.out.println("posForward耗时：" + (endMicro - startMicro) / 1000);//3305
        System.out.println(content.substring(posForward));
        System.out.println("==================================");
        long startMicro2 = System.nanoTime();
        int posBackward = findPosBackward(content, patternB, power, start);
        long endMicro2 = System.nanoTime();
        System.out.println("posBackward耗时：" + (endMicro2 - startMicro2) / 1000);//2335
        System.out.println(content.substring(0, posBackward));
        System.out.println("==================分割线==================");
        long startMicro3 = System.nanoTime();
        int posForwardExt = expandForward(content, patternF, power, start);
        long endMicro3 = System.nanoTime();
        System.out.println("posForwardExt耗时：" + (endMicro3 - startMicro3) / 1000);//4104
        System.out.println(content.substring(posForwardExt));
        System.out.println("==================================");
        long startMicro4 = System.nanoTime();
        int posBackwardExt = expandBackward(content, patternB, power, start);
        long endMicro4 = System.nanoTime();
        System.out.println("posBackwardExt耗时：" + (endMicro4 - startMicro4) / 1000);//5444
        System.out.println(content.substring(0, posBackwardExt));
        System.out.println("==================================");
        long startMicro5 = System.nanoTime();
        Map.Entry<Integer, Integer> globalPos = findGlobalPos(content, patternB, power, start);
        long endMicro5 = System.nanoTime();
        System.out.println("posBackwardExt耗时：" + (endMicro5 - startMicro5) / 1000);//3212
        System.out.println(content.substring(globalPos.getKey(), globalPos.getValue()));
        System.out.println("==================================");
        long startMicro6 = System.nanoTime();
        Map.Entry<Integer, Integer> globalPosExt = findGlobalPos(content, patternB, power, start);
        long endMicro6 = System.nanoTime();
        System.out.println("posBackwardExt耗时：" + (endMicro6 - startMicro6) / 1000);
        System.out.println(content.substring(globalPosExt.getKey(), globalPosExt.getValue()));//3093

    }

}
